local function gen_vertices(player, width, height, Steps, desaturation)
	local Song
	local first_step_has_occurred = false
	local pn = ToEnumShortString(player)

	if not Steps then
		if GAMESTATE:IsCourseMode() then
			local TrailEntry = GAMESTATE:GetCurrentTrail(player):GetTrailEntry(GAMESTATE:GetCourseSongIndex())
			Steps = TrailEntry:GetSteps()
		else
			Steps = GAMESTATE:GetCurrentSteps(player)
		end
	end
	Song = SONGMAN:GetSongFromSteps(Steps)

	if not Steps or not Song then return {} end

	-- This function does no work if we already have the data in SL.Streams cache.
	ParseChartInfo(Steps, pn)
	PeakNPS = SL[pn].Streams.PeakNPS
	NPSperMeasure = SL[pn].Streams.NPSperMeasure 
	-- store the PeakNPS in GAMESTATE:Env()[pn.."PeakNPS"] in case both players are joined
	-- their charts may have different peak densities, and if they both want histograms,
	-- we'll need to be able to compare densities and scale one of the graphs vertically
	GAMESTATE:Env()[pn.."PeakNPS"] = PeakNPS

	-- use MESSAGEMAN to broadcast that the peak NPS has been calculated (and/or updated in CourseMode)
	-- and is available.  actors on the current screen can listen for this via something like:
	--
	-- PeakNPSUpdatedMessageCommand=function(self)
	--   local p1peak = GAMESTATE:Env()["P1PeakNPS"]
	-- end
	MESSAGEMAN:Broadcast("PeakNPSUpdated")

	local verts = {}
	local x, y, t

	if (PeakNPS and NPSperMeasure and #NPSperMeasure > 1) then

		local TimingData = Steps:GetTimingData()
		local FirstSecond = math.min(TimingData:GetElapsedTimeFromBeat(0), 0)
		local LastSecond = Song:GetLastSecond()

		-- magic numbers obtained from Photoshop's Eyedrop tool in rgba percentage form (0 to 1)
		local blue   = {0,    0.678, 0.753, 1}
		local purple = {0.51, 0,     0.631, 1}

		if desaturation ~= nil then
			local function Desaturate(color, desaturation)
				local luma = 0.3 * color[1] + 0.59 * color[2] + 0.11 * color[3]
				color[1] = color[1] + desaturation * (luma - color[1])
				color[2] = color[2] + desaturation * (luma - color[2])
				color[3] = color[3] + desaturation * (luma - color[3])
				return color
			end
			blue = Desaturate(blue, desaturation)
			purple = Desaturate(purple, desaturation)
		end

		local upper

		for i, nps in ipairs(NPSperMeasure) do

			if nps > 0 then first_step_has_occurred = true end

			if first_step_has_occurred then
				-- i will represent the current measure number but will be 1 larger than
				-- it should be (measures in SM start at 0; indexed Lua tables start at 1)
				-- subtract 1 from i now to get the actual measure number to calculate time
				t = TimingData:GetElapsedTimeFromBeat((i-1)*4)

				x = scale(t, FirstSecond, LastSecond, 0, width)
				y = round(-1 * scale(nps, 0, PeakNPS, 0, height))

				-- if the height of this measure is the same as the previous two measures
				-- we don't need to add two more points (bottom and top) to the verts table,
				-- we can just "extend" the previous two points by updating their x position
				-- to that of the current measure.  For songs with long streams, this should
				-- cut down on the overall size of the verts table significantly.
				if #verts > 2 and verts[#verts][1][2] == y and verts[#verts-2][1][2] == y then
					verts[#verts][1][1] = x
					verts[#verts-1][1][1] = x
				else
					-- lerp_color() is a global function defined by the SM engine that takes three arguments:
					--    a float between [0,1]
					--    color1
					--    color2
					-- and returns a color that has been linearly interpolated by that percent between the two colors provided
					-- for example, lerp_color(0.5, yellow, orange) will return the color that is halfway between yellow and orange
					upper = lerp_color(math.abs(y/height), blue, purple )

					verts[#verts+1] = {{x, 0, 0}, blue} -- bottom of graph (blue)
					verts[#verts+1] = {{x, y, 0}, upper}  -- top of graph (somewhere between blue and purple)
				end
			end
		end
	end

	return verts
end

-- FIXME: add inline comments explaining the intent/purpose of this code
function interpolate_vert(v1, v2, offset)
	local ratio = (offset - v1[1][1]) / (v2[1][1] - v1[1][1])
	local y = v1[1][2] * (1 - ratio) + v2[1][2] * ratio
	local color = lerp_color(ratio, v1[2], v2[2])

	return {{offset, y, 0}, color}
end


function NPS_Histogram(player, width, height, desaturation)
	local pn = ToEnumShortString(player)
	local amv = Def.ActorMultiVertex{
		InitCommand=function(self)
			self:SetDrawState({Mode="DrawMode_QuadStrip"})
		end,
		["CurrentSteps"..pn.."ChangedMessageCommand"]=function(self)
			self:queuecommand("Redraw")
		end,
		RedrawCommand=function(self)
			-- we've reached a new song, so reset the vertices for the density graph
			-- this will occur at the start of each new song in CourseMode
			-- and at the start of "normal" gameplay
			local verts = gen_vertices(player, width, height, nil, desaturation)
			self:SetNumVertices(#verts):SetVertices(verts)
		end
	}

	return amv
end

-- density graph that does not use CurrentSongChangedMessage
function NPS_Histogram_Static(player, width, height)
	local amv = Def.ActorMultiVertex{
		Name="DensityGraph_AMV",
		InitCommand=function(self)
			self:SetDrawState({Mode="DrawMode_QuadStrip"})
			self:queuecommand("SetVertices")
		end,
		SetVerticesCommand=function(self)
			local verts = gen_vertices(player, width, height)
			self:SetNumVertices(#verts):SetVertices(verts)
		end
	}

	return amv
end

-- set of density graphs for a course
-- one little issue here is that varying nps per song isn't reflected by the relative height of each chart
-- honestly too big of a hassle for me to mess with right now
function NPS_Histogram_Static_Course(player, width, height)
	local af = Def.ActorFrame{}
	local trail = GAMESTATE:GetCurrentTrail(player)
	
	-- first get the total time
	local totaltime = TotalCourseLength(player)
	
	-- build a table of offsets and widths (doing one loop with everything in InitCommand will just use
	-- the last value whatever local variable in the loop was once the actors execute)
	local curx = 0
	local ptable = {}
	for te in ivalues(trail:GetTrailEntries()) do
		local w = (te:GetSong():GetLastSecond() / totaltime) * width
		table.insert(ptable, {curx, w, te:GetSteps()})
		curx = curx + w
	end
	for i, pos in ipairs(ptable) do
		-- add a transparent backing quad for every other song to differentiate one from the next
		if i % 2 == 0 then
			af[#af+1] = Def.Quad{
				InitCommand = function(self)
					self:horizalign("left"):x(pos[1]):vertalign("bottom"):zoomto(pos[2], height)
					:diffuse(1,1,1,0.075)
				end
			}
		end
		-- add density graph amv
		af[#af+1] = Def.ActorMultiVertex{
			InitCommand = function(self)
				self:x(pos[1])
				self:SetDrawState({Mode="DrawMode_QuadStrip"})
				self:queuecommand("SetVertices")
			end,
			SetVerticesCommand = function(self)
				local verts = gen_vertices(player, pos[2], height, pos[3])
				self:SetNumVertices(#verts):SetVertices(verts)
			end
		}
	end

	return af
end

-- density graph for song select
function MusicWheel_NPS_Histogram(player, width, height)
	local pn = ToEnumShortString(player)
	local amv = Def.ActorMultiVertex{
		InitCommand=function(self)
			self:SetDrawState({Mode="DrawMode_QuadStrip"})
			self:queuecommand("SetBlank")
		end,
		CurrentSongChangedMessageCommand = function(self)
			self:stoptweening()
			self:queuecommand("SetBlank")
			self:sleep(0.5)
			self:queuecommand("SetVertices")
		end,
		["CurrentSteps"..pn.."ChangedMessageCommand"] = function(self)
			self:stoptweening()
			self:queuecommand("SetBlank")
			self:sleep(0.5)
			self:queuecommand("SetVertices")
		end,
		SetVerticesCommand=function(self)
			if GAMESTATE:IsCourseMode() then return end
			if not GAMESTATE:GetCurrentSong() then return end
			local verts = gen_vertices(player, width, height)
			self:SetNumVertices(#verts):SetVertices(verts)
			-- broadcast message so that bd text can respond
			MESSAGEMAN:Broadcast("StreamsChanged"..pn)
		end,
		SetBlankCommand = function(self)
			self:SetNumVertices(0):SetVertices({})
			MESSAGEMAN:Broadcast("StreamsCleared"..pn)
		end
	}

	return amv
end


function Scrolling_NPS_Histogram(player, width, height, desaturation)
	local verts, visible_verts
	local left_idx, right_idx

	local amv = Def.ActorMultiVertex{
		InitCommand=function(self)
			self:SetDrawState({Mode="DrawMode_QuadStrip"})
		end,
		UpdateCommand=function(self)
			if visible_verts ~= nil then
				self:SetNumVertices(#visible_verts):SetVertices(visible_verts)
				visible_verts = nil
			end
		end,

		LoadCurrentSong=function(self, scaled_width)
			verts = gen_vertices(player, scaled_width, height, nil, desaturation)

			left_idx = 1
			right_idx = 2
			self:SetScrollOffset(0)
		end,
		SetScrollOffset=function(self, offset)
			local left_offset = offset
			local right_offset = offset + width

			for i = left_idx, #verts, 2 do
				if verts[i][1][1] >= left_offset then
					left_idx = i
					break
				end
			end

			for i = right_idx, #verts, 2 do
				if verts[i][1][1] <= right_offset then
					right_idx = i
				else
					break
				end
			end

			visible_verts = {unpack(verts, left_idx, right_idx)}

			if left_idx > 1 then
				local prev1, prev2, cur1, cur2 = unpack(verts, left_idx-2, left_idx+1)
				table.insert(visible_verts, 1, interpolate_vert(prev1, cur1, left_offset))
				table.insert(visible_verts, 2, interpolate_vert(prev2, cur2, left_offset))
			end

			if right_idx < #verts then
				local cur1, cur2, next1, next2 = unpack(verts, right_idx-1, right_idx+2)
				table.insert(visible_verts, interpolate_vert(cur1, next1, right_offset))
				table.insert(visible_verts, interpolate_vert(cur2, next2, right_offset))
			end
		end
	}

	return amv
end
